package com.demo491_递增子序列;

import java.util.*;

/**
 * 这个和求子集问题很像，  但是  不可以进行一个排序。   求递增子序列。
 */
public class Solution {
    public static void main(String[] args) {
        int[] ints={1,1,1,1,1,1,1};
        List<List<Integer>> list = findSubsequences(ints);
        for (int i = 0; i < list.size(); i++) {
            System.out.println(list.get(i));
        }
    }
    public static List<List<Integer>> findSubsequences(int[] nums) {
        ArrayList<Integer> path = new ArrayList<>();
        List<List<Integer>> arrayLists = new ArrayList<>();
        dfs(nums,path,arrayLists,0);

        return arrayLists;
    }

    private static void dfs(int[] nums, ArrayList<Integer> path, List<List<Integer>> arrayLists, int startIndex) {
        // 收集结果
        // 只要这个集合中的个数 >= 2 , 就可以进行一个结果的搜集
        if (path.size()>=2){
            ArrayList<Integer> temp = new ArrayList<>();
            for (Integer item : path) {
                temp.add(item);
            }
            // 把该集合加入到这个集合中
            arrayLists.add(temp);
        }

        // 终止条件
        if (startIndex== nums.length){   //  当然这里不写这个也是可以的, 因为这里的话, 我们当startIndex >= nums.length 的时候,这个后面的for循环是会自动结束的
            return;
        }

        /**
         * 整体可以, 但是去重逻辑稍微显得有点复杂,  改进用set去重.  但是内存消耗估计不低吧 ~
         */

        // 横向遍历 + 纵向递归
        for (int i = startIndex; i < nums.length; i++) {
            // 树层去重:  之前取过的元素后面就不能再取了.  那么判断原则, 就是比如: [4,7,6,7] 这个数组前面取了这个 4 , 然后现在的
            // 数组就是这个[7,6,7] , 如果 取到7 的时候, 前面有取到过7 , 那么后面遇到这个7的时候, 判断一下前面的数组中是不是有7 ,
            // 并且为了区分这个 树枝去重 和 树层去重, 应该要让这个  如果存在的 i的范围是在这个    startIndex  =<  j  < i
            boolean flag= false;
            if (i>=1){
                for (int j = i-1; j >=startIndex ; j--) {
                    if (nums[i]==nums[j]){
                        flag = true;
                        break;
                    }
                }
            }

            if (flag){
                continue;
            }
            // 对当前元素进行一个判断处理
            if (path.size()>0 && nums[i]<path.get(path.size()-1)){
                // 如果当前元素是一个小于集合中的最后一个元素的, 那么进行一个跳过
                continue;
            }

            // 把当前元素加入集合中
            path.add(nums[i]);
            // 递归
            dfs(nums,path,arrayLists,i+1);
            // 回溯
            path.remove(path.size()-1);
        }
    }
}
